#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    void _combinationSumR(vector<vector<int>>& ret, vector<int>& v, vector<int>& candidates, int& target, int start)
    {
        if (target == 0)
        {
            ret.push_back(v);
            return;
        }
        for (int i = start; i < candidates.size(); i++)
        {
            if (target < 0)
                break;
            v.push_back(candidates[i]);
            target -= candidates[i];
            _combinationSumR(ret, v, candidates, target, i);
            target += candidates[i];
            v.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> v;
        _combinationSumR(ret, v, candidates, target, 0);
        return ret;
    }
};

class Solution {
public:
    void _combinationSum2R(vector<vector<int>>& ret, vector<int>& v, vector<int>& candidates, int& target, int start)
    {
        if (target == 0)
        {
            ret.push_back(v);
            return;
        }
        for (int i = start; i < candidates.size(); i++)
        {
            if(target<0)
                break;
            if (i > start && candidates[i] == candidates[i - 1])
                continue;
                v.push_back(candidates[i]);
            target -= candidates[i];
            _combinationSum2R(ret, v, candidates, target, i + 1);
            v.pop_back();
            target += candidates[i];
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ret;
        vector<int> v;
        _combinationSum2R(ret, v, candidates, target, 0);
        return ret;
    }
};

class Solution {
public:
    bool ispalindrome(string& word, int begin, int end)
    {
        while (begin < end)
        {
            if (word[begin++] != word[end--])
                return false;
        }
        return true;
    }

    void _partitionR(vector<vector<string>>& ret, vector<string> v, string& s, int start)
    {
        if (start == s.size())
        {
            ret.push_back(v);
        }
        for (int i = start; i < s.size(); i++)
        {
            if (ispalindrome(s, start, i))
            {
                string str(s.begin() + start, s.begin() + i + 1);
                v.push_back(str);
            }
            else
                continue;
            _partitionR(ret, v, s, i + 1);
            v.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        vector<string> v;
        _partitionR(ret, v, s, 0);
        return ret;
    }
};